Valid Triangle Number

LeetCode 611 | Difficulty: Medium

Medium

Problem Description

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

- `1 <= nums.length <= 1000`

- `0 <= nums[i] <= 1000`

Topics: Array, Two Pointers, Binary Search, Greedy, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 202 ms)

Metric	Value
Runtime	202 ms
Memory	38.1 MB
Date	2022-02-03

Solution

public class Solution {
    public int TriangleNumber(int[] nums) {
        Array.Sort(nums);
    int n = nums.Length;
    int count = 0;
    for (int k = n-1; k >= 0; k--)
    {
        for (int i = 0, j= k-1; i < j; )
        {
            if(nums[i]+nums[j] > nums[k])
            {
                count += j-i;
                j--;
            }
            else i++;
        }
    }
    return count;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Precisely define what the left and right boundaries represent, and the loop invariant.